package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.CommonsGraph.findShortestPath
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

class BellmannFordTestCase {
    /**
     * Test Graph and Dijkstra's solution can be seen on
     * [Wikipedia](http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/)
     */
    @Test
    fun testFindShortestPathAndVerify() {
        // the input graph
        val graph =
            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val one = BaseLabeledVertex("1")
        val two = BaseLabeledVertex("2")
        val three = BaseLabeledVertex("3")
        val four = BaseLabeledVertex("4")
        val five = BaseLabeledVertex("5")

        graph.addVertex(one)
        graph.addVertex(two)
        graph.addVertex(three)
        graph.addVertex(four)
        graph.addVertex(five)

        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 2", 6.0), two)
        graph.addEdge(one, BaseLabeledWeightedEdge("1 -> 4", 7.0), four)

        graph.addEdge(two, BaseLabeledWeightedEdge("2 -> 3", 5.0), three)
        graph.addEdge(two, BaseLabeledWeightedEdge("2 -> 5", -4.0), five)
        graph.addEdge(two, BaseLabeledWeightedEdge("2 -> 4", 8.0), four)

        graph.addEdge(three, BaseLabeledWeightedEdge("3 -> 2", -2.0), two)

        graph.addEdge(four, BaseLabeledWeightedEdge("4 -> 3", -3.0), three)
        graph.addEdge(four, BaseLabeledWeightedEdge("4 -> 5", 9.0), five)

        graph.addEdge(five, BaseLabeledWeightedEdge("5 -> 3", 7.0), three)
        graph.addEdge(five, BaseLabeledWeightedEdge("5 -> 1", 2.0), one)

        // the expected weighted path
        val expected = InMemoryWeightedPath(one, three, DoubleWeightBaseOperations, BaseWeightedEdge())
        expected.addConnectionInTail(one, BaseLabeledWeightedEdge("1 -> 4", 7.0), four)
        expected.addConnectionInTail(four, BaseLabeledWeightedEdge("4 -> 3", -3.0), three)

        // the actual weighted path
        val allVertexPairsShortestPath: AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(one)
                .applyingBelmannFord(DoubleWeightBaseOperations)

        val actual =
            allVertexPairsShortestPath.findShortestPath(one, three)
        Assert.assertEquals(expected, actual)
    }

    @Test(expected = PathNotFoundException::class)
    fun testNotConnectGraph() {
        var a: BaseLabeledVertex? = null
        var b: BaseLabeledVertex? = null
        // the actual weighted path
        var allVertexPairsShortestPath: AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>? = null
        try {
            val graph =
                UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

            a = BaseLabeledVertex("a")
            b = BaseLabeledVertex("b")
            graph.addVertex(a)
            graph.addVertex(b)

            allVertexPairsShortestPath = findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(a)
                .applyingBelmannFord(DoubleWeightBaseOperations)
        } catch (e: PathNotFoundException) {
            Assert.fail(e.message)
        }
        allVertexPairsShortestPath!!.findShortestPath(a!!, b!!)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        // the actual weighted path
//        findShortestPath(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .applyingBelmannFord(DoubleWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullMonoid() {
//        var graph: UndirectedMutableGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>? = null
//        var a: BaseLabeledVertex? = null
//        try {
//            graph = UndirectedMutableGraph()
//
//            a = BaseLabeledVertex("a")
//            val b = BaseLabeledVertex("b")
//            graph.addVertex(a)
//            graph.addVertex(b)
//        } catch (e: NullPointerException) {
//            Assert.fail(e.message)
//        }
//
//        // the actual weighted path
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(a)
//            .applyingBelmannFord(null)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullVertices() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .applyingBelmannFord(DoubleWeightBaseOperations)
//    }
}
